// Copyright (C) 2024 wlly-lzh
// Created by wlly-lzh on 24-4-5
// Binary Tree  二叉树

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "linkedqueue.c"

typedef struct LBinTree LBinTree;
struct LBinTree {
	void *Data;
	LBinTree * Left;
	LBinTree * Right;
	LBinTree * Parent;
};

void Error_BinTree_Malloc();
void Error_BinTree_Null();
void Error_BinTree_Path();
void Free_LBinTree_call(LBinTree *Tree,void (*FreeData)(void *));
void PreOrderTraverse_LBinTree_call(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V);
void InOrderTraverse_LBinTree_call(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V);
void PostOrderTraverse_LBinTree_call(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V);
void LevelOrderTraverse_LBinTree_call(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V);

LBinTree * Init_LBinTree(){
	LBinTree * newTree;
	newTree =(LBinTree *)malloc(sizeof(LBinTree));
	if(newTree == NULL){
		Error_BinTree_Malloc();
		exit(3);
	}
	newTree->Data=NULL;
	newTree->Left=newTree->Right=NULL;
	newTree->Parent=NULL;
	return newTree;
}

LBinTree * Create_LBinTree(void * Data){
	LBinTree * newTree=Init_LBinTree();
	newTree->Data=Data;
	return newTree;
}

bool Assign_BinTree(LBinTree *Tree,char *Path,void *Data,
		void (*FreeData)(void *)){
	if(Tree == NULL){
		Error_BinTree_Null();
		exit(4);
	}
	int i=0;
	if(Path[i] != '/' && Path[i] != '0'){
		Error_BinTree_Path();
		return false;
	}
	if(Path[1] == '\0'){ // 路径只有一层
		if(Tree->Data != NULL)
			(*FreeData)(Tree->Data);
		Tree->Data=Data;
		return true;
	}
	for(i=1; Path[i+1]!='\0'; ++i){
		if(Path[i] == '0'){
			if(Tree != NULL){
				Tree=Tree->Right;
			}
			else{
				Error_BinTree_Path();
				return false;
			}
		}else if(Path[i] == '1'){
			if(Tree != NULL){
				Tree=Tree->Left;
			}else{
				Error_BinTree_Path();
				return false;
			}
		}else{
			Error_BinTree_Path();
			return false;
		}
	}
	if(Path[i] == '0'){
		if(Tree->Right == NULL){
			Tree->Right=Create_LBinTree(Data);
			Tree->Right->Parent=Tree;
		}else{
			(*FreeData)(Tree->Right->Data);
			Tree->Right->Data=Data;
		}
	}else if(Path[i] == '1'){
		if(Tree->Left == NULL){
			Tree->Left=Create_LBinTree(Data);
			Tree->Left->Parent=Tree;
		}else{
			(*FreeData)(Tree->Left->Data);
			Tree->Left->Data=Data;
		}
	}else{
		Error_BinTree_Path();
		return false;
	}
	return true;
}

void PreOrderTraverse_LBinTree(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V){
	if(Tree != NULL){
		PreOrderTraverse_LBinTree_call(Tree,Vist,V);
	}else{
		Error_BinTree_Null();
		exit(4);
	}
}

void InOrderTraverse_LBinTree(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V){
	if(Tree != NULL){
		InOrderTraverse_LBinTree_call(Tree,Vist,V);
	}else{
		Error_BinTree_Null();
		exit(4);
	}
}

void PostOrderTraverse_LBinTree(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V){
	if(Tree != NULL){
		PostOrderTraverse_LBinTree_call(Tree,Vist,V);
	}else{
		Error_BinTree_Null();
		exit(4);
	}
}
void LevelOrderTraverse_LBinTree(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V){
	if(Tree != NULL){
		LevelOrderTraverse_LBinTree_call(Tree,Vist,V);
	}else{
		Error_BinTree_Null();
		exit(4);
	}
}

void Destroy_LBinTree(LBinTree **Tree,void (*FreeData)(void *)){
	if(Tree == NULL || *Tree == NULL){
		Error_BinTree_Null();
		exit(4);
	}
	Free_LBinTree_call(*Tree,FreeData);
	*Tree=NULL;
}
void Clear_LBinTree(LBinTree *Tree,void (*FreeData)(void *)){
	if(Tree == NULL){
		Error_BinTree_Null();
		exit(4);
	}
	Free_LBinTree_call(Tree->Left,FreeData);
	Free_LBinTree_call(Tree->Right,FreeData);
}
/*------------------------------------------------------------------*/
// 内部调用函数
void Free_LBinTree_call(LBinTree *Tree,void (*FreeData)(void *)){
	if(Tree != NULL){
		Free_LBinTree_call(Tree->Left,FreeData);
		Free_LBinTree_call(Tree->Right,FreeData);
		(*FreeData)(Tree->Data);
		free(Tree);
	}
}
void PreOrderTraverse_LBinTree_call(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V){
	(*Vist)(Tree->Data,V);
	if(Tree->Left != NULL)
		PreOrderTraverse_LBinTree_call(Tree->Left,Vist,V);
	if(Tree->Right !=NULL)
		PreOrderTraverse_LBinTree_call(Tree->Right,Vist,V);
}
void InOrderTraverse_LBinTree_call(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V){
	if(Tree->Left != NULL)
		InOrderTraverse_LBinTree_call(Tree->Left,Vist,V);
	(*Vist)(Tree->Data,V);
	if(Tree->Right != NULL)
		InOrderTraverse_LBinTree_call(Tree->Right,Vist,V);
}
void PostOrderTraverse_LBinTree_call(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V){
	if(Tree->Left != NULL)
		PostOrderTraverse_LBinTree_call(Tree->Left,Vist,V);
	if(Tree->Right != NULL)
		PostOrderTraverse_LBinTree_call(Tree->Right,Vist,V);
	(*Vist)(Tree->Data,V);
}
void LevelOrderTraverse_LBinTree_call(LBinTree *Tree,
		void (*Vist)(void *,void *),void *V){
	LinkedQueue * Queue;
	Queue=Create_LinkedQueue();
	En_LinkedQueue(Queue,Tree);
	while(Length_LinkedQueue(Queue) > 0){
		De_LinkedQueue(Queue,(void *)&Tree);
		if(Tree->Left != NULL)
			En_LinkedQueue(Queue,Tree->Left);
		if(Tree->Right != NULL)
			En_LinkedQueue(Queue,Tree->Right);
		(*Vist)(Tree->Data,V);
	}
	Destroy_LinkedQueue(&Queue);
}
/*------------------------------------------------------------------*/
#ifdef _LINUX_PLATFORM_
void Error_BinTree_Null(){
	printf("\033[31mliblds/BinTree: Your paramete Is Null!\033[0m\n");
}
void Error_BinTree_Malloc(){
	printf("\033[31mliblds/BinTree: Malloc False!\033[0m\n");
}
void Error_BinTree_Path(){
	printf("\033[31mliblds/BinTree: The Path is Error!\033[0m\n");
}
#else
void Error_BinTree_Null(){
	printf("liblds/BinTree: Your paramete Is Null!\n");
}
void Error_BinTree_Malloc(){
	printf("liblds/BinTree: Malloc False!\n");
}
void Error_BinTree_Path(){
	printf("liblds/BinTree: The Path is Error!\n");
}
#endif
